﻿using System; 


class Puzzle15
{	
	public static void Swap(ref string a, ref string b)
	{
		string tmp = a; 
		a = b; 
		b = tmp;
	}
	
	public static void FisherYatesShuffle(ref string[] array)
	{
		Random r = new Random(); 
		
		for (byte i = (byte)(array.Length - 1); i > 0; i--)
		{
			byte index = (byte)r.Next(i);
			Swap(ref array[index], ref array[i]);
		}
	}
	
	public static void InitGameBoard(ref string[,] gameBoard, string[] tileValues)
	{
		byte t = 0; 
		
		for (byte row = 0; row < gameBoard.GetLength(0); row++)
			for (byte col = 0; col < gameBoard.GetLength(1); col++)
				gameBoard[row, col] = tileValues[t++];		
	}
	
	public static void DisplayGameBoard(string[,] gameBoard)
	{
		for (byte row = 0; row < gameBoard.GetLength(0); row++)
		{
			for (byte col = 0; col < gameBoard.GetLength(1); col++)
			{
				Console.Write('|' + gameBoard[row, col] + '|' + "\t");
			}
			
			Console.WriteLine();
		}
	}
	
	public static void HandleTileMovement(string tileValue, ref string[,] gameBoard)
	{
		byte tvRow = 0, tvCol = 0, etRow = 0, etCol = 0;
		
		for (byte row = 0; row < gameBoard.GetLength(0); row++)
			for (byte col = 0; col < gameBoard.GetLength(1); col++)	
			{
				if (gameBoard[row, col] == tileValue)
				{
					tvRow = row;
					tvCol = col;
				}
				
				else if (gameBoard[row, col] == " ")
				{
					etRow = row; 
					etCol = col;
				}
			}
	
			byte endRow = tvRow; 
			byte endCol = tvCol; 
			
			if (etRow == tvRow && etCol > tvCol)
			{
				while (etCol > endCol)
					Swap(ref gameBoard[etRow, etCol], ref gameBoard[etRow, --etCol]);
			}
			
			else if (etCol < endCol)
			{
				while (etCol < endCol)
					Swap(ref gameBoard[etRow, etCol], ref gameBoard[etRow, ++etCol]);
			}
			
			if (etCol == tvCol && etRow > tvRow)
			{
				while (etRow > endRow)
					Swap(ref gameBoard[etRow, etCol], ref gameBoard[--etRow, etCol]);
			}
			
			else if (etRow < tvRow)
			{
				while (etRow < endRow)
					Swap(ref gameBoard[etRow, etCol], ref gameBoard[++etRow, etCol]);
			}
	}
	
	
	public static bool CheckForWinningConfig(string[,] gameBoard)
	{
		bool isWinning = true; 
		
		string[,] winningConfig = {{"1", "2", "3", "4"},
									{"5", "6", "7", "8"},
									{"9", "10", "11", "12"},
									{"13", "14", "15", " "}};
		
		for (int row = 0; row < gameBoard.GetLength(0); row++)
		  for (int col = 0; col < gameBoard.GetLength(1); col++)
			if (gameBoard[row, col] != winningConfig[row, col])
			  isWinning = false; 
				    
		return isWinning;
	 }
	
	static void Main()
	{
		const byte rows = 4, cols = 4;
		uint numberOfMoves = 0; 
		
		string[,] gameBoard = new string[rows, cols];
		
		string[] tileValues = {"1", "2", "3", "4", "5", "6", "7", "8", 
							   "9", "10", "11", "12", "13", "14", "15", " "};
		
		FisherYatesShuffle(ref tileValues); 
		InitGameBoard(ref gameBoard, tileValues);
		
		string userInput = String.Empty;
		
		while (!CheckForWinningConfig(gameBoard))
		{
			DisplayGameBoard(gameBoard);
			userInput = Console.ReadLine();
			HandleTileMovement(userInput, ref gameBoard);
			numberOfMoves++; 
		}
		
		Console.WriteLine("You won! It took you {0} number of shuffles: ", numberOfMoves);
		Console.ReadKey(); 
	}
}